﻿#include "SeqList.h"

//打印顺序表
void SeqListPrint(SeqList* psl)
{   //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
//顺序表初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);

	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
//顺序表销毁、释放内存
void SeqListDestroy(SeqList* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl)
{
	// ˣҪ
	if (psl->size == psl->capacity)
	{   //relloc扩容
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可

		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}

}

//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	//psl->a[psl->size - 1] = 0;  
	//此语句是将删除后的覆盖为0，但这样做不太好
	//原因：1.若原有最后一个为0，意义不大  2.若类型不为int，而是double或char，覆盖为0有误
	//因为size标识有效数据，因此即使删除，数据还在capacity，即使删除后没有被覆盖，但不会访问
	if (psl->size > 0)
	{
		psl->size--;
	}
}


//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	// 挪动数据，腾出头部空间
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}

	psl->a[0] = x;
	psl->size++;

	//SeqListInsert(psl, 0, x);

}


//顺序表头删
void SeqListPopFront(SeqList* psl)
{

	assert(psl);
	if (psl->size > 0)
	{
		//挪动数据覆盖删除
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}
		--psl->size;

	}

}


// 在pos(指定位置）插入x
//void SeqListInsert(SeqList* psl, int pos, SLDataType x)    //解决整型提升形成的死循环,解决1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	// 暴力检查
	assert(psl);
	// 温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d\n", pos);
		return;
		//exit(-1);  //直接终止程序，没必要
	}
	// 暴力检查
	//assert(pos <= psl->size);

	//检查后，根据需要是否增容
	SeqListCheckCapacity(psl);

	//解决整型提升形成的死循环,解决2
	//int end = psl->size-1;
	//while (end >=(int)pos)
	//{
	//	psl->a[end+1] = psl->a[end];
	//	--end;
	//}

	//解决整型提升形成的死循环,解决3
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

// 删除pos(指定位置）的数据
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);//此处间接判断（psl->size > 0）

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}
//按值查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}
////按值查找-打印版(待完善）
//int SeqListFind(SeqList* psl, SLDataType x)
//{
//	assert(psl);
//
//	for (int i = 0; i < psl->size; ++i)
//	{
//		if (psl->a[i] == x)
//		{
//			printf("查找的值：%d", psl->a[i]);
//			printf("\n");
//			return i;
//		}
//	}
//
//	return -1;
//}

//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;
}